The present invention relates generally to systems and methods for enabling a user using a host computer to securely log onto a server computer even in the presence of eavesdroppers and other forms of security attacks.
While there are many different password authentication protocols, they all solve the same problem: one party must somehow prove to another party that he knows a password p, which might have been set in advance. These protocols vary from the trivial to the incredibly complex, and many offer some form of protection from various attacks mounted by third parties.
Password protection has been the cornerstone of multiuser system security for decades. The advent of networking has given users convenient and transparent remote access to their systems. It has also created a whole new set of problems for people who use public networks to access these systems, because such networks are vulnerable to passive snooping and to some degree, active interference.
The present invention addresses these issues with a protocol that can be safely negotiated over an insecure network without compromising system security and which has several other useful properties not present in other commonly-used authentication protocols. Some of these properties make the present invention uniquely suitable for integration with existing system security applications.
All multiuser systems need some mechanism to identify which users are allowed to access the system and what privileges those users have. Nearly all such systems require that the user type in some sort of secret string, referred to as a password, that presumably is known only to that user. When the user identifies himself at login time, the system asks him for his password, and if he enters it correctly, the system gives him access to his account. This works fine when users are sitting at the console of the machine or at terminals connected directly to it, but networked systems are troublesome because even an inexperienced intruder can monitor the activity on a network fairly easily. Since most systems carry out the login and password exchange without encryption, anyone can xe2x80x9csnoopxe2x80x9d the network while someone logs in, capture their usemame and password as they are typed, and impersonate that user at a later time on that system.
Although networking has been commonplace for over a decade, most modem multiuser systems still do not employ any built-in form of encryption to prevent passwords from being snooped. Instead, there exist a variety of add-on products that attempt to address the security problems associated with networks. They offer varying degrees of protection from different kinds of potential attacks, but they generally require both users and administrators to take extra steps to achieve this security. Some of them require that the user maintain an entire list of passwords or keep key files on the client side for use by the authentication software.
The present invention relates to direct password authentication. Mechanisms that fall into this category of authentication cannot rely on persistent stored information stored on the client side. The user""s password, which is a memorized quantity, is the only secret available to the client software. It is assumed that the network between the client and server is vulnerable to both eavesdropping and deliberate tampering. In addition, no trusted third party such as a key server or arbitrator can be used; only the original two parties can engage in the authentication protocol.
The present invention distinguishes itself from the rest of the field by offering features long thought to be unattainable simultaneously:
Secure against passive snooping. A passive attacker cannot obtain any information that would enable him to authenticate successfully to the server. This includes immunity to replay attacks.
End-to-end session encryption. An intruder cannot monitor a user""s activities or xe2x80x9chijackxe2x80x9d an authenticated session. In other words, any attempt to tamper with the network connection and to hijack an authenticated session will fail.
Forward secrecy and compromise containment. A captured password cannot be used to compromise past or currently encrypted sessions. A broken or compromised session key will not help an attacker deduce or even make guesses at the password.
Two-party operation. Neither a trusted third party nor a secure, central key server is needed.
Password-only client-side operation. Users do not need to maintain any files or keys on the client side. They only need to input their password to the client login program.
No secret information stored on the server. The password file stored on the server can be made public with little or no impact on system security. Very few secure protocols permit this, and those that do invariably fail to meet one or more of the other requirements.
The last two features taken together allow the protocol of the present invention to be used as a general-purpose remote and local authenticated login system, augmenting or even replacing the utilities now found on most operating systems.
For the rest of this document, computer login security will be described with reference to the following set of hypothetical characters and the computer system 100 shown in FIG. 1:
Steve operates the network""s server 102.
Carol, a user sitting at a client machine/terminal 104, wishes to log in remotely to the server 102 belonging to Steve.
Since Steve knows Carol, he has given her some privileges that an ordinary (and potentially hostile) user on the system, like Henry, doesn""t have.
Henry is also a user of the system who assesses the server using another client machine or terminal 106. However, Henry would like nothing more than to gain access to Carol""s account, if for no better reason than to use all those fancy privileges and read Carol""s e-mail.
Eve is an eavesdropper who has managed to install some packet sniffing software on her computer 108, which happens to be located on the network between Carol""s client computer 104 and Steve""s server 102.
Mallory works for a rival company and has a client computer 110 with direct access to the same network (and more resources). He can intercept, alter, and inject messages into the network at will, and he can make any of his messages appear to come from anywhere he chooses.
In other words, Carol""s computer 104 is a client, and Steve""s computer 102 is the server. Alice is another friendly party requiring parallel access to the system. Henry is a hostile user who already has access to the system but who seeks access to Carol""s account. Eve is conducting passive (eavesdropping) attacks over the network, while Mallory is conducting active (malicious) attacks.
It is assumed that Henry, Eve, and Mallory are cooperating and can exchange information freely, while Steve and Carol might not be able to meet very often and do not have any other means of secure communication that cannot be compromised by Eve or Mallory.
The server computer 102 includes a central processing unit 120, memory 122 and a network interface (NIC) 124. The memory 122, which will typically include both random access memory (RAM) and non-volatile memory (e.g., disk storage), stores:
an operating system 126;
a server side password authentication procedure 128, used for verifying that user asking to log onto the server are who they claim to be;
a password file 130, which may be a publicly accessible file (i.e., readable by all users of the system 100) containing password information for each authorized users of the system;
client files 132, including programs and data belonging to the various authorized users of the server 102.
As will be described in more detail below, the password information in the password file 130 for each user may be the users public key, or the hash of the user""s password, or some other value that can be used to verify a user""s asserted password without revealing the password itself.
Carol""s client computer 104 includes a central processing unit 140, memory 142, a network interface (NIC) 144, and a user interface 146 (e.g., including a display, keyboard, pointer device, and so on). The memory 142, which will typically include both random access memory (RAM) and non-volatile memory (e.g., disk storage), stores:
an operating system 150;
a client side login procedure 152, used for logging onto the server; and other programs and data not relevant to the present discussion.
As in the real world, Eve, Mallory, and Henry have quite a few options for compromising system security. Attacks can be classified based on the following categories:
Passive attacks are based on information that an intruder observes being exchanged between Carol and Steve. For this scenario, Eve will be mostly responsible for these attacks. Passive attacks are considered to be easy to carry out; anyone with access to any of the networks between Carol and Steve can monitor traffic with minimal difficulty, so it is important that a protocol not be susceptible to such attacks.
Active attacks involve some form of manipulation of the network between Carol and Steve. Examples include intercepting, substituting, or replaying packets, or forging entire messages that appear to come from one party. Mallory will carry out active attacks under this scenario. These attacks require much more effort to carry out and are generally considered less of a threat for a typical system. Nevertheless, there are some situations in which such an attack becomes feasible, so an authentication protocol should guard against them as well.
Off-line attacks are carried out in their entirety without directly involving Carol or Steve. For example, making a copy of Steve""s password file and running a password-cracking program on it constitutes an off-line attack, since the attack does not require either Carol or Steve to be active while the attack takes place.
On-line attacks can only take place with at least one of the parties active. The obvious example would be for an intruder to attempt to log in to Steve""s system repeatedly, guessing different passwords each time. All systems can be attacked this way, and it is assumed that the inefficiency of these attacks, coupled with the high possibility of detection given suitable precautions, makes them impractical.
External attacks are mounted by agents who are untrusted and unknown to Carol and Steve. They only have access to information that is advertised as xe2x80x9cpublic.xe2x80x9d For the purposes of this document, any information that is sent over the public network between Carol and Steve will fall into this category. Either Eve or Mallory could execute an external attack.
Internal attacks can be carried out by someone who already has some kind of access to either end of the protocol. Examples might be other people who have access to the client or server hosts. Obviously, these are more difficult to prevent than external attacks. In our scenarios, only Henry has the access needed for an internal attack.
All of the known attacks fall into one or more of the above categories. Furthermore, some of the attacks discussed later can take advantage of a compromise of some other part of the system. Such conditions will be noted where applicable.
Many existing systems authenticate session participants by sending a password from the client to the server in cleartext or by encoding it with an easily reversible transform. This is highly insecure, as Eve could easily obtain Carol""s password by eavesdropping.
xe2x80x9cChallenge-responsexe2x80x9d systems provide slightly more security, by requiring the client to respond to a randomly-generated challenge from the server. These protocols, however, are universally subject to brute-force attack against the secret password. To fix this, the system must use some form of private key storage, like a smartcard, which loses the convenience benefits of a password-only system. Related systems like S/Key and Kerberos all suffer from this weakness. In addition, these systems store plaintext-equivalent information in the password file, making a compromise of the password file potentially disastrous.
The newest systems, up until now, have been xe2x80x9cpublic-key-assistedxe2x80x9d authentication schemes, like the Secure Shell (ssh) and the Secure Socket Layer (SSL). These protocols attempt to set up a secure channel between client and server, and use this channel to send the password to the server. While this resists passive attacks better than challenge-response protocols, the practice of encrypting before authentication is actually a subtle protocol design error. It allows active attacks such as the xe2x80x9cman-in-the-middlexe2x80x9d attack, allowing Mallory to intercept the password in some cases. This can be prevented by resorting to a public-key or certificate infrastructure, but is potentially expensive and difficult to maintain for a simple login method.
The Diffie-Heliman protocol, described in U.S. Pat. No. 4,200,770, is an unauthenticated key agreement protocol. While not specifically designed for login management, it is easily adapted for that purpose. In Diffie-Hellman, the two parties each generate a public/private key pair (e.g., Carol generates public/private key pair xp and xs, and Steve computes a public/private key pair yp an ys), typically selecting the private key randomly. The two parties exchange their public keys and then each generate an identical session key, S, as follows:
S=ypxs mod N (computed by Carol)
S=xpys mod N (computed by Steve)
This is usually used as part of a public-key assisted system. Once both sides agree on the session key, a normal login session is performed with all communications being encrypted using the session key as a symmetric encryption key, which protects the password and all other communications from eavesdroppers.
Like any public-key assisted protocol, however, Diffie-Hellman is not secure against active attacks like the xe2x80x9cman-in-the-middlexe2x80x9d attack, in which an interloper (e.g., Mallory) intercepts all communications between Steve and Carol, conducts a valid-looking session with each, and develops two session keys, one for each party. While Carol and Steve think they are communicating securely with each other, Mallory is actually decrypting and re-encrypting all their communications, including any passwords.
Up until know, attempts at creating a secure, authenticated variant of Dfffie-Hellman have resulted in protocols that are still vulnerable to some form of active attack or that require a high-entropy shared secret. The present invention solves these problems and maintains the user-level convenience necessary to replace the standard login mechanism for most modem operating systems.
In summary, the present invention is a system and method for a server computer and a login procedure executed by a client host computer to establish a session key in a manner that is secure against both passive and active security attacks, and which utilizes the user""s password so as to enable the server to determine whether or not the user in fact knows the password for the usemame account specified by the user during the login process.
Prior to a login session, the server computer stores a password verification value xp for each of a plurality of authorized users of the server computer. Each user generates a password verification value xp by applying a first one-way hashing function to a password p specified by the user to generate a secret value xs, and then applying a second one-way function to the secret value xs to generate xp.
When a client computer attempts to establish a login session between the server computer and client computer, the following steps are performed. The server computer receives a user identifier from the client computer, and retrieves the password verification value stored by the server for the user. The client computer generates a first secret value ws and then generates a corresponding first public value wp by applying the second one-way function to the first secret value ws. The client computer sends the first public value wp to the server computer.
The server computer generates a second secret value ys and then generates a corresponding second public value yp by applying the second one-way function to the second secret value ys. The server computer sends the second public value yp to the client computer. The server computer also generates a server session key K1 by applying a first predefined session key generation function to the first public value wp, the retrieved password verification value xp, and the second secret value ys.
The client computer regenerates the user""s secret value xs, and then generates a client session key K2 by applying a second predefined session key generation function to the second public value yp, the first secret value ws, and the regenerated secret value xs.
Then the client and server computers exchange a set of messages so that each can verify that the other computer""s session key is equal to its locally generated session key. The login session is established only if the server computer verifies that the server and client session keys match.